package leetcode101.double_pointer;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code5
 * @Description 524. Longest Word in Dictionary through Deleting
 * Given a string s and a string array dictionary, return the longest string in the dictionary
 * that can be formed by deleting some of the given string characters.
 * If there is more than one possible result, return the longest word with the smallest lexicographical order.
 * If there is no possible result, return the empty string.
 *
 * Example 1:
 *
 * Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * Output: "apple"
 *
 * Example 2:
 *
 * Input: s = "abpcplea", dictionary = ["a","b","c"]
 * Output: "a"
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-27 15:27
 */
public class Code5 {
    public static void main(String[] args) {
        List<String> dictionary = new ArrayList<>();
        dictionary.add("ale");
        dictionary.add("appla");
        dictionary.add("apple");
        dictionary.add("monkey");
        dictionary.add("appld");
        dictionary.add("plea");
        System.out.println(findLongestWord("abpcplea", dictionary));
    }

    public static String findLongestWord(String s, List<String> dictionary) {
        /*
        首先对字典进行排序，按照长度从长倒短排序，如果长度相等则按照字典顺序排序
         */
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() > o2.length()) {
                    return -1;
                }
                if (o1.length() < o2.length()) {
                    return 1;
                }
                return o1.compareTo(o2);
            }
        };
        dictionary.sort(comparator);

        int srcPointer, tempPointer;
        for (String str : dictionary) {
            srcPointer = 0;
            tempPointer = 0;
            while (srcPointer < s.length() && tempPointer < str.length()) {
                if (s.charAt(srcPointer) != str.charAt(tempPointer)) {
                    srcPointer++;
                } else {
                    srcPointer++;
                    tempPointer++;
                }
            }
            if (tempPointer >= str.length()) {
                return str;
            }
        }
        return "";
    }
}
